package leetcode.code0397;

import java.util.HashMap;
import java.util.Map;

public class Solution397 {
	// java.lang.StackOverflowError
	public int integerReplacement(int n) {
		Map<Integer, Integer> dp = new HashMap<>();
		if (n == Integer.MAX_VALUE) {
			return f(((n - 1) >> 1) + 1, dp) + 2;
		}
		return this.f(n, dp);
	}

	private int f(int n, Map<Integer, Integer> dp) {
		if (n == 1) {
			return 0;
		}
		if (dp.containsKey(n)) {
			return dp.get(n);
		}
		int ans = 0;
		if ((n & 1) == 0) {
			ans = f(n >> 1, dp) + 1;
		} else {
			ans = Math.min(f(n - 1, dp) + 1, f((n + 1) >> 1, dp) + 2);
		}
		dp.put(n, ans);
		return ans;
	}

	public int it(int n) {
		int ans = 0;
		while (n > 1) {
			if ((n & 1) == 0) {
				ans = it(n >> 1) + 1;
			} else {
				ans = Math.min(it(n - 1) + 1, it((n + 1) >> 1) + 2);
			}
		}
		return ans;
	}

	public int integerReplacement2(int n) {
		int[] dp = new int[n + 2];
		dp[1] = 0;
		for (int i = 2; i <= n; i++) {
			if ((i & 1) == 0) {
				dp[i] = dp[i >> 1] + 1;
			} else {
				dp[i] = Math.min(dp[i - 1] + 1, dp[(i + 1) >> 1] + 2);
			}
		}
		return dp[n];
	}

	public static void main(String[] args) {
		Solution397 so = new Solution397();
		int ans = so.integerReplacement(Integer.MAX_VALUE);
		System.out.println(ans);
//		ans = so.integerReplacement(7);
//		System.out.println(ans);
		int max = Integer.MAX_VALUE;
		int a = 1073741824;
		int b = (max - 1) / 2 + 1;
		System.out.println(a == b);
	}

}
